Next: Composing Patterns in Rewrite Rules, Previous: Algebraic Properties of Rewrite Rules, Up: Rewrite Rules [Contents][Index]
Certain “function names” serve as markers in rewrite rules. Here is a complete list of these markers. First are listed the markers that work inside a pattern; then come the markers that work in the righthand side of a rule.
One kind of marker, ‘import(x)’, takes the place of a whole rule. Here ‘x’ is the name of a variable containing another rule set; those rules are “spliced into” the rule set that imports them. For example, if ‘[f(a+b) := f(a) + f(b), f(a b) := a f(b) :: real(a)]’ is stored in variable ‘linearF’, then the rule set ‘[f(0) := 0, import(linearF)]’ will apply all three rules. It is possible to modify the imported rules slightly: ‘import(x, v1, x1, v2, x2, …)’ imports the rule set ‘x’ with all occurrences of ‘v1’, as either a variable name or a function name, replaced with ‘x1’ and so on. (If ‘v1’ is used as a function name, then ‘x1’ must be either a function name itself or a ‘< >’ nameless function; see Specifying Operators.) For example, ‘[g(0) := 0, import(linearF, f, g)]’ applies the linearity rules to the function ‘g’ instead of ‘f’. Imports can be nested, but the import-with-renaming feature may fail to rename sub-imports properly.
The special functions allowed in patterns are:
This pattern matches exactly ‘x’; variable names in ‘x’ are not interpreted as meta-variables. The only flexibility is that numbers are compared for numeric equality, so that the pattern ‘f(quote(12))’ will match both ‘f(12)’ and ‘f(12.0)’. (Numbers are always treated this way by the rewrite mechanism: The rule ‘f(x,x) := g(x)’ will match ‘f(12, 12.0)’. The rewrite may produce either ‘g(12)’ or ‘g(12.0)’ as a result in this case.)
Here ‘x’ must be a function call
‘f(x1,x2,…)’. This pattern
matches a call to function ‘f’ with
the specified argument patterns. No special knowledge of the
properties of the function ‘f’ is
used in this case; ‘+’ is not
commutative or associative. Unlike quote, the
arguments ‘x1,x2,…’ are
treated as patterns. If you wish them to be treated
“plainly” as well, you must enclose them with
more plain markers:
‘plain(plain(-a
) + plain(b c))’.
Here ‘x’ must be a variable name. This must appear as an argument to a function or an element of a vector; it specifies that the argument or element is optional. As an argument to ‘+’, ‘-’, ‘*’, ‘&&’, or ‘||’, or as the second argument to ‘/’ or ‘^’, the value def may be omitted. The pattern ‘x + opt(y)’ matches a sum by binding one summand to ‘x’ and the other to ‘y’, and it matches anything else by binding the whole expression to ‘x’ and zero to ‘y’. The other operators above work similarly.
For general miscellaneous functions, the default value
def must be specified. Optional arguments are
dropped starting with the rightmost one during matching. For
example, the pattern ‘f(opt(a,0), b,
opt(c,b))’ will match
‘f(b)’,
‘f(a,b)’, or
‘f(a,b,c)’. Default values of zero
and ‘b’ are supplied in this example
for the omitted arguments. Note that the literal variable
‘b’ will be the default in the
latter case, not the value that matched the
meta-variable ‘b’. In other words,
the default def is effectively quoted.
This matches the pattern ‘x’, with the attached condition ‘c’. It is the same as ‘x :: c’.
This matches anything that matches both pattern ‘x’ and pattern ‘y’. It is the same as ‘x &&& y’. see Composing Patterns in Rewrite Rules.
This matches anything that matches either pattern ‘x’ or pattern ‘y’. It is the same as ‘x ||| y’.
This matches anything that does not match pattern ‘x’. It is the same as ‘!!! x’.
This matches any vector of one or more elements. The first element is matched to ‘h’; a vector of the remaining elements is matched to ‘t’. Note that vectors of fixed length can also be matched as actual vectors: The rule ‘cons(a,cons(b,[])) := cons(a+b,[])’ is equivalent to the rule ‘[a,b] := [a+b]’.
This is like cons, except that the
last element is matched to
‘h’, with the remaining elements
matched to ‘t’.
This matches any function call. The name of the function,
in the form of a variable, is matched to
‘f’. The arguments of the function,
as a vector of zero or more objects, are matched to
‘args’. Constants, variables, and
vectors do not match an apply pattern.
For example, ‘apply(f,x)’ matches
any function call,
‘apply(quote(f),x)’ matches any call
to the function ‘f’,
‘apply(f,[a,b])’ matches any
function call with exactly two arguments, and
‘apply(quote(f), cons(a,cons(b,x)))’
matches any call to the function ‘f’
with two or more arguments. Another way to implement the
latter, if the rest of the rule does not need to refer to the
first two arguments of ‘f’ by name,
would be ‘apply(quote(f), x :: vlen(x) >=
2)’. Here’s a more interesting sample use
of apply:
apply(f,[x+n]) := n + apply(f,[x]) :: in(f, [floor,ceil,round,trunc]) :: integer(n)
Note, however, that this will be slower to match than a
rule set with four separate rules. The reason is that Calc
sorts the rules of a rule set according to top-level function
name; if the top-level function is apply, Calc
must try the rule for every single formula and sub-formula.
If the top-level function in the pattern is, say,
floor, then Calc invokes the rule only for
sub-formulas which are calls to floor.
Formulas normally written with operators like
+ are still considered function calls:
apply(f,x) matches
‘a+b’ with ‘f =
add’, ‘x = [a,b]’.
You must use apply for meta-variables with
function names on both sides of a rewrite rule:
‘apply(f, [x]) := f(x+1)’ is
not correct, because it rewrites
‘spam(6)’ into
‘f(7)’. The righthand side should be
‘apply(f, [x+1])’. Also note that
you will have to use No-Simplify mode (m O) when
entering this rule so that the apply isn’t
evaluated immediately to get the new rule ‘f(x)
:= f(x+1)’. Or, use s e to enter the
rule without going through the stack, or enter the rule as
‘apply(f, [x]) := apply(f, [x+1]) :: 1
’. See Conditional
Rewrite Rules.
This is used for applying rules to formulas with selections; see Selections with Rewrite Rules.
Special functions for the righthand sides of rules are:
The notation ‘quote(x)’ is
changed to ‘x’ when the righthand
side is used. As far as the rewrite rule is concerned,
quote is invisible. However, quote
has the special property in Calc that its argument is not
evaluated. Thus, while it will not work to put the rule
‘t(a) := typeof(a)’ on the stack
because ‘typeof(a)’ is evaluated
immediately to produce ‘t(a) :=
100’, you can use quote to protect
the righthand side: ‘t(a) :=
quote(typeof(a))’. (See Conditional
Rewrite Rules, for another trick for protecting rules
from evaluation.)
Special properties of and simplifications for the function
call ‘x’ are not used. One
interesting case where plain is useful is the
rule, ‘q(x) := quote(x)’, trying to
expand a shorthand notation for the quote
function. This rule will not work as shown; instead of
replacing ‘q(foo)’ with
‘quote(foo)’, it will replace it
with ‘foo’! The correct rule would
be ‘q(x) := plain(quote(x))’.
Where ‘t’ is a vector, this is
converted into an expanded vector during rewrite processing.
Note that cons is a regular Calc function which
normally does this anyway; the only way cons is
treated specially by rewrites is that cons on
the righthand side of a rule will be evaluated even if
default simplifications have been turned off.
Analogous to cons except putting
‘h’ at the end of the
vector ‘t’.
Where ‘f’ is a variable and
args is a vector, this is converted to a function
call. Once again, note that apply is also a
regular Calc function.
The formula ‘x’ is handled in the
usual way, then the default simplifications are applied to it
even if they have been turned off normally. This allows you
to treat any function similarly to the way cons
and apply are always treated. However, there is
a slight difference: ‘cons(2+3, [])’
with default simplifications off will be converted to
‘[2+3]’, whereas
‘eval(cons(2+3, []))’ will be
converted to ‘[5]’.
The formula ‘x’ has meta-variables substituted in the usual way, then algebraically simplified.
The formula ‘x’ has meta-variables substituted in the normal way, then “extendedly” simplified as if by the a e command.
There are also some special functions you can use in conditions.
The expression ‘x’ is evaluated
with meta-variables substituted. The algebraic
simplifications are not applied by default, but
‘x’ can include calls to
evalsimp or evalextsimp as
described above to invoke higher levels of simplification.
The result of ‘x’ is then bound to
the meta-variable ‘v’. As usual, if
this meta-variable has already been matched to something else
the two values must be equal; if the meta-variable is new
then it is bound to the result of the expression. This
variable can then appear in later conditions, and on the
righthand side of the rule. In fact,
‘v’ may be any pattern in which case
the result of evaluating ‘x’ is
matched to that pattern, binding any meta-variables that
appear in that pattern. Note that let can only
appear by itself as a condition, or as one term of an
‘&&’ which is a whole
condition: It cannot be inside an
‘||’ term or otherwise buried.
The alternate, equivalent form ‘let(v,
x)’ is also recognized. Note that the use of
‘:=’ by let, while
still being assignment-like in character, is unrelated to the
use of ‘:=’ in the main part of a
rewrite rule.
As an example, ‘f(a) := g(ia) :: let(ia :=
1/a) :: constant(ia)’ replaces
‘f(a)’ with
‘g’ of the inverse of
‘a’, if that inverse exists and is
constant. For example, if ‘a’ is a
singular matrix the operation ‘1/a’
is left unsimplified and
‘constant(ia)’ fails, but if
‘a’ is an invertible matrix then the
rule succeeds. Without let there would be no way
to express this rule that didn’t have to invert the
matrix twice. Note that, because the meta-variable
‘ia’ is otherwise unbound in this
rule, the let condition itself always
“succeeds” because no matter what
‘1/a’ evaluates to, it can
successfully be bound to ia.
Here’s another example, for integrating cosines of
linear terms: ‘myint(cos(y),x) := sin(y)/b ::
let([a,b,x] := lin(y,x))’. The lin
function returns a 3-vector if its argument is linear, or
leaves itself unevaluated if not. But an unevaluated
lin call will not match the 3-vector on the
lefthand side of the let, so this
let both verifies that y is linear,
and binds the coefficients a and b
for use elsewhere in the rule. (It would have been possible
to use ‘sin(a x + b)/b’ for the
righthand side instead, but using
‘sin(y)/b’ avoids gratuitous
rearrangement of the argument of the sine.)
Similarly, here is a rule that implements an
inverse-erf function. It uses root
to search for a solution. If root succeeds, it
will return a vector of two numbers where the first number is
the desired solution. If no solution is found,
root remains in symbolic form. So we use
let to check that the result was indeed a
vector.
ierf(x) := y :: let([y,z] := root(erf(a) = x, a, .5))
The meta-variable v, which must already have
been matched to something elsewhere in the rule, is compared
against pattern p. Since matches is a
standard Calc function, it can appear anywhere in a
condition. But if it appears alone or as a term of a
top-level ‘&&’, then you get
the special extra feature that meta-variables which are bound
to things inside p can be used elsewhere in the
surrounding rewrite rule.
The only real difference between ‘let(p := v)’ and ‘matches(v, p)’ is that the former evaluates ‘v’ using the default simplifications, while the latter does not.
This is actually a variable, not a function. If
remember appears as a condition in a rule, then
when that rule succeeds the original expression and rewritten
expression are added to the front of the rule set that
contained the rule. If the rule set was not stored in a
variable, remember is ignored. The lefthand side
is enclosed in quote in the added rule if it
contains any variables.
For example, the rule ‘f(n) := n f(n-1) ::
remember’ applied to
‘f(7)’ will add the rule
‘f(7) := 7 f(6)’ to the front of the
rule set. The rule set EvalRules works slightly
differently: There, the evaluation of
‘f(6)’ will complete before the
result is added to the rule set, in this case as
‘f(7) := 5040’. Thus
remember is most useful inside
EvalRules.
It is up to you to ensure that the optimization performed
by remember is safe. For example, the rule
‘foo(n) := n :: evalv(eatfoo) > 0 ::
remember’ is a bad idea (evalv is
the function equivalent of the = command); if the
variable eatfoo ever contains 1, rules like
‘foo(7) := 7’ will be added to the
rule set and will continue to operate even if
eatfoo is later changed to 0.
Remember the match as described above, but only if condition ‘c’ is true. For example, ‘remember(n % 4 = 0)’ in the above factorial rule remembers only every fourth result. Note that ‘remember(1)’ is equivalent to ‘remember’, and ‘remember(0)’ has no effect.
Next: Composing Patterns in Rewrite Rules, Previous: Algebraic Properties of Rewrite Rules, Up: Rewrite Rules [Contents][Index]